#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define LEN 8

typedef struct node {
	int data;
	struct node *left;
	struct node *right;
} node_t;

void tree_insert(node_t **root, int data)
{
	node_t *new, **pos = NULL;

	new = (node_t *)malloc(sizeof(node_t));
	memset(new, 0, sizeof(node_t));
	new->data = data;
	
	pos = root;	
	while (*pos) {
		if (data < (*pos)->data)
			pos = &(*pos)->left;
		else
			pos = &(*pos)->right;
	}
	*pos = new;
}

void reverse_tree_1(node_t *root)
{
	node_t *l, *r;
	l = root->left;
	r = root->right;

	root->left = r;
	root->right = l;

	if (r)
		reverse_tree_1(r);
	if (l)
		reverse_tree_1(l);
}

void in_order_scan(node_t *node)
{
	if (node->left)
		in_order_scan(node->left);
	printf("%d ", node->data);
	if (node->right)
		in_order_scan(node->right);
}

/* Start: code for stack */
typedef struct {
	node_t* arr[LEN];
	int pos;
}stack_t;

void init_stack(stack_t *s)
{
	s->pos = 0;
}

void push(stack_t *s, node_t *node)
{
	s->arr[(s->pos)++] = node;
}

node_t *pop(stack_t *s)
{
	return s->arr[--(s->pos)];
}

int is_empty(stack_t *s)
{
	if (s->pos > 0)
		return 0;
	return 1;
}

/* End: code for stack */

/* Start: code for reverse without recursion */
void reverse_tree_2(node_t *node)
{
	if (!node)
		return;
	stack_t s[1];

	push(s, node);
	while(!is_empty(s)) {
		node_t *tmp = NULL;
		node = pop(s);
		
		tmp = node->left;
		node->left = node->right;
		node->right = tmp;

		if (node->left)
			push(s, node->left);
		if (node->right)
			push(s, node->right);
	}
}
/* End: code for reversion without recursion */

int main()
{
	int data[LEN] = {6, 7, 4, 9, 3, 2, 5, 1};
	int i;
	node_t *root = NULL;

	for (i = 0; i < LEN; i++) {
		tree_insert(&root, data[i]);
	}
	in_order_scan(root);
	printf("\n");
	reverse_tree_1(root);
	in_order_scan(root);
	printf("\n");
	reverse_tree_2(root);
	in_order_scan(root);
	printf("\n");

	return 0;
}

